package sort;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 七大排序
 *
 * @author 是阿秋啊
 * @date 2022/03/17 09:03
 **/
public class SevenSort {
    private static final ThreadLocalRandom random = ThreadLocalRandom.current();

    //快速排序1
    public static void quickSort(int[] arr) {
        quickSortInternal(arr, 0, arr.length - 1);
    }

    //二路快排
    public static void quickSort2(int[] arr) {
        quickSortInternal2(arr, 0, arr.length - 1);
    }

    //三路快排
    public static void quickSort3(int[] arr) {
        quickSortInternal3(arr, 0, arr.length - 1);
    }

    private static void quickSortInternal3(int[] arr, int l, int r) {
        if (r - l <= 15) {
            insertionSort(arr, l, r);
            return;
        }
        int randomIndex = random.nextInt(l, r);
        swap(arr, l, randomIndex);
        int v = arr[l];
        // 这些变量的取值，一定是满足区间的定义，最开始的时候，所有区间都是空
        // arr[l + 1..lt] < v
        // lt是指向最后一个<v的元素
        int lt = l;
        // arr[lt + 1..i) == v
        // i - 1是最后一个 = v的元素
        int i = l + 1;
        // arr[gt..r] > v
        // gt是第一个 > v的元素
        int gt = r + 1;
        // i从前向后扫描和gt重合时，所有元素就处理完毕
        while (i < gt) {
            if (arr[i] < v) {
                // arr[l + 1..lt] < v
                // arr[lt + 1..i) == v
                swap(arr, i, lt + 1);
                lt++;
                i++;
            } else if (arr[i] > v) {
                // 交换到gt - 1
                swap(arr, i, gt - 1);
                gt--;
                // 此处i不++，交换来的gt - 1还没有处理
            } else {
                // 此时arr[i] = v
                i++;
            }
        }
        // lt落在最后一个 < v的索引处
        swap(arr, l, lt);
        // arr[l..lt - 1] < v
        quickSortInternal3(arr, l, lt - 1);
        // arr[gt..r] > v
        quickSortInternal3(arr, gt, r);
    }

    private static void quickSortInternal2(int[] arr, int l, int r) {
        if (r - l <= 15) {
            insertionSort(arr, l, r);
            return;
        }
        int p = partition2(arr, l, r);
        quickSortInternal2(arr, l, p - 1);
        quickSortInternal2(arr, p + 1, r);
    }

    /**
     * 二路快排的分区
     * 在arr[l..r]上进行分区处理
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partition2(int[] arr, int l, int r) {
        int randomIndex = random.nextInt(l, r);
        swap(arr, l, randomIndex);
        int v = arr[l];
        int i = l + 1;
        int j = r;
        while (true) {
            while (i <= j && arr[i] < v) {
                i++;
            }
            while (i <= j && arr[j] > v) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }

    /**
     * 在arr[l...r]上进行快速排序
     *
     * @param arr
     * @param l
     * @param r
     */
    private static void quickSortInternal(int[] arr, int l, int r) {
        if (r - l <= 15) {
            insertionSort(arr, l, r);
            return;
        }
        //先获取分区点
        //分区点就是经过函数分区后，某个元素落在了最终的位置
        //分区点左侧小于该元素的区间，右侧大与该元素的区间
        int p = partition(arr, l, r);
        quickSortInternal(arr, l, p - 1);
        quickSortInternal(arr, p + 1, r);
    }

    /**
     * 在arr[l..r]上的分区函数，返回分区点的索引
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partition(int[] arr, int l, int r) {
        //随机在当前数组中选一个数
        int randomIndex = random.nextInt(l, r);
        swap(arr, l, randomIndex);
        int v = arr[l];
        // arr[l + 1..j] < v
        // arr[j + 1..i) >= v
        // i表示当前正在扫描的元素
        // j指向的是比v小的元素，j + 1指向的是第一个比v大或等于的元素
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v) {
                swap(arr, i, j + 1);
                j++;
            }
        }
        swap(arr, j, l);
        return j;
    }

    /**
     * 快速排序非递归，用栈的实现
     *
     * @param arr
     */
    public static void quickSortNonRecursion(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        //栈中保存当前集合的开始位置和终止位置
        int l = 0;
        int r = arr.length - 1;
        stack.push(r);
        stack.push(l);
        while (!stack.isEmpty()) {
            //栈不为空时，说明子区间还没有处理完毕
            int left = stack.pop();
            int right = stack.pop();
            if (left >= right) {
                continue;
            }
            int p = partition(arr, left, right);
            //依次将右区间的开始和结束位置入栈
            stack.push(right);
            stack.push(p + 1);
            stack.push(p - 1);
            stack.push(left);
        }
    }

    /**
     * 归并排序
     *
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        mergeSortInternal(arr, 0, arr.length - 1);
    }

    /**
     * 在arr[r...l]上进行归并排序
     *
     * @param arr 区间数组
     * @param l   区间左索引
     * @param r   区间右索引
     */
    private static void mergeSortInternal(int[] arr, int l, int r) {
        //未优化
//        if (l >= r) {
//            //当前数组只剩一个元素，归过程结束
//            return;
//        }
        //优化2
        if (r - l <= 15) {
            //小区间使用插入排序
            insertionSort(arr, l, r);
            return;
        }
        int mid = l + ((r - l) >> 1);
        // 将原数组拆分为左右两个小区间，分别递归进行
        //走完这个函数之后arr的左区间已经有序
        mergeSortInternal(arr, l, mid);
        //走完这个函数之后arr的右区间已经有序
        mergeSortInternal(arr, mid + 1, r);
        //优化1
        //只有当两个左右子区间还有先后顺序不同时merge并
        if (arr[mid] > arr[mid + 1]) {
            merge(arr, l, mid, r);
        }
    }

    /**
     * 归并排序非递归方法
     *
     * @param arr
     */
    public static void mergeSortNonRecursion(int[] arr) {
        // 最外层循环表示每次合并的子数组的元素个数
        for (int sz = 1; sz <= arr.length; sz += sz) {
            // 内层循环的变量i表示每次合并的开始索引
            // i + sz 就是右区间的开始索引，i + sz < arr.length说明还存在右区间
            for (int i = 0; i + sz < arr.length; i += sz + sz) {
                merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, arr.length - 1));
            }
        }
    }

    /**
     * 在arr[l...r]区间进行插入排序
     *
     * @param arr
     * @param l
     * @param r
     */
    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            for (int j = i; j > l && arr[j] < arr[j - 1]; j--) {
                swap(arr, j, j - 1);
            }
        }
    }

    /**
     * 合并两个子数组arr[l...mid] 和 arr[mid + 1 ... r]
     * 为一个大的有序数组arr[l...r]
     *
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        //先创建一个新的临时数组aux
        int[] aux = new int[r - l + 1];
        //将arr元素值拷贝到aux上
        for (int i = 0; i < aux.length; i++) {
            //加l是因为实际数组偏移量
            aux[i] = arr[i + l];
        }
        //左侧数组开始索引
        int i = l;
        //右侧数组开始索引
        int j = mid + 1;
        //k表示当前正在合并的原数组的索引下表
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 左侧区间已经处理完毕，只需要将右侧区间值拷贝到原数组即可
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {
                // 右侧区间已经处理完毕，只需要将左侧区间值拷贝到原数组即可
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l] <= aux[j - l]) {
                //此时左侧区间的元素较小，相等元素放在左区间，保证稳定性
                arr[k] = aux[i - l];
                i++;
            } else {
                // 右侧区间元素较小
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    /**
     * 希尔排序
     *
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int gap = arr.length >> 1;
        while (gap > 1) {
            insertionSortBygap(arr, gap);
            gap >>= 1;
        }
        //gap == 1的情况
        insertionSortBygap(arr, 1);
    }

    /**
     * 按照gap分组进行插入排序
     *
     * @param arr
     * @param gap
     */
    private static void insertionSortBygap(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            // 不断向前扫描相同gap的元素
            // j - gap 从j位置开始向前还有相同步数的元素
            for (int j = i; j - gap >= 0 && arr[j] < arr[j - gap]; j -= gap) {
                swap(arr, j, j - gap);
            }
        }
    }

    /**
     * 直接插入排序
     * 每次从无序区间中拿一个值插入到已经排序好的区间的合适位置，直到整个数组有序
     *
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        //刚开始默认第一个元素为有序区间
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                } else {
                    //此时说明arr[j] >= arr[j - 1]说明已经找到位置，arr[j]已经有序 -- 直接下一次循环
                    break;
                }
            }
            //内部循环也可写为
//            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
//                swap(arr, j, j - 1);
//            }
        }
    }

    //折半插入查找
    public static void insertionSortBS(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int val = arr[i];
            int left = 0;
            int right = i;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (arr[mid] > val) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            //搬移比待插入元素大的元素--left...i的元素
            for (int j = i; j > left; j--) {
                arr[j] = arr[j - 1];
            }
            arr[left] = val;
        }
    }

    /**
     * 选择排序
     *
     * @param arr 待排序数组
     */
    public static void selectionSort(int[] arr) {
        // 最开始，无序区间[0...n] 有序空间[]
        // 当无序区间只剩下一个元素时，整个集合已经有序
        for (int i = 0; i < arr.length - 1; i++) {
            // min变量存储了当前的最小值索引
            int min = i;
            //从剩下的元素中选择最小值
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            // min这个索引一定对应了当前无序区间中找到的最小值，换到无序区间最前面i
            swap(arr, i, min);
        }
    }

    //双向选择排序
    public static void selectionSortOP(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        // low = high,无序区间只剩下一个元素，此时数组已经有序
        while (low <= high) {
            int min = low;
            int max = low;
            for (int i = low + 1; i <= high; i++) {
                if (arr[min] > arr[i]) {
                    min = i;
                }
                if (arr[max] < arr[i]) {
                    max = i;
                }
            }
            //此时min索引一定是无序空间内最小值索引，与low交换
            swap(arr, low, min);
            if (max == low) {
                //此时最大值的位置已经被替换到索引为min的位置
                max = min;
            }
            swap(arr, max, high);
            low++;
            high--;
        }
    }

    /**
     * 冒牌排序
     *
     * @param arr 待排序数组
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean isSwaped = true;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    isSwaped = false;
                }
            }
            if (isSwaped) break;
        }
    }

    /**
     * 堆排序
     *
     * @param arr
     */
    public static void heapSort(int[] arr) {
        // 1.先将arr进行heapify调整为最大堆
        // 从最后一个非叶子节点开始进行siftDown操作
        for (int i = ((arr.length - 1 - 1) / 2); i >= 0; i--) {
            siftDown(arr, i, arr.length);
        }
        //此时arr变为最大堆
        for (int i = (arr.length - 1); i > 0; i--) {
            //arr[0] 堆顶元素，就是当前堆的最大值
            swap(arr, 0, i);
            //下沉操作长度根据i变换是因为，通过循环不断将最大值依次倒着放入数组末尾，所以不再对操作过的末尾进行操作
            siftDown(arr, 0, i);
        }
    }

    /**
     * 元素下沉操作
     *
     * @param arr    操作数组
     * @param i      当前要下沉的索引
     * @param length 数组长度
     */
    private static void siftDown(int[] arr, int i, int length) {
        while (2 * i + 1 < length) {
            int j = 2 * i + 1;
            if (j + 1 < length && arr[j] < arr[j + 1]) {
                j = j + 1;
            }
            //此时j是i的左右子树最大值
            if (arr[i] > arr[j]) {
                break;
            } else {
                swap(arr, i, j);
                i = j;
            }
        }
    }

    /**
     * 数组元素交换操作
     *
     * @param arr 交换数组
     * @param i   交换位置
     * @param j   交换位置
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {7, 5, 4, 3, 2, 1, 9, 10, 8, 6};
//        heapSort(arr);
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
